package 链表和树.二叉树;

import java.util.ArrayDeque;
import java.util.Deque;

//Java：找树左下角的值
public class FindBottomLeftTreeValue{
    public static void main(String[] args) {
        Solution solution = new FindBottomLeftTreeValue().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
class Solution {
        //两种做法 1.层序遍历到最后一层第一个元素就是
    //2. 我们改为从右到左遍历 这样遍历完以后最后一个元素就是了
    public int findBottomLeftValue(TreeNode root) {

        TreeNode node = root;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);

        while (!q.isEmpty()){
            node = q.poll(); //注意这里全局变量记录，局部变量出了域就会销毁
            if(node.right != null) q.add(node.right);//只需要右儿子先进左儿子后进就可以达到效果
            if(node.left != null) q.add(node.left);
        }
        return node.val;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}